﻿using System;
using System.Collections.Generic;
using System.Text;

namespace CSLearn
{
    public class Solution
    {

        /// <summary>
        /// 2549  统计桌面上的不同数字
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public int DistinctIntegers(int n)
        {
            Queue<int> queue = new Queue<int>();
            queue.Enqueue(n);
            HashSet<int> visited = new HashSet<int>();
            visited.Add(n);
            while (queue.Count > 0)
            {
                int num = queue.Dequeue();
                for (int i = 1; i < num; i++)
                {
                    if(num % i == 1 && !visited.Contains(i))
                    {
                        queue.Enqueue(i);
                        visited.Add(i);
                    }
                }
            }
            return visited.Count;
        }

        /// <summary>
        /// leetcode  1793  好子数组的最大分数(双指针, 贪心 / Solution)
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public int MaximumScore(int[] nums, int k)
        {
            int n = nums.Length;
            int left = k, right = k;
            int res = 0;
            int temp = nums[k];
            while (true)
            {
                while (left >= 0 && nums[left] >= temp)
                    left--;
                while (right < n && nums[right] >= temp)
                    right++;
                res = Math.Max(res, (right - left + 1) * temp);
                if (left < 0 && right >= n) break;
                if (left < 0) temp = nums[right];
                else if (right >= n) temp = nums[left];
                else temp = Math.Min(nums[left], nums[right]);
                break;
            }
            return res;
        }

        // leetcode  303  区域和检索 - 数组不可变(前缀和)
        int[] sum;
        public void NumArray(int[] nums)
        {
            int n = nums.Length;
            sum = new int[n + 1];
            for (int i = 0; i < n; i++)
            {
                sum[i + 1] = sum[i] + nums[i];
            }
        }

        public int SumRange(int left, int right)
        {
            return sum[right + 1] - sum[left];
        }

        /// <summary>
        /// leetcode  11  盛最多水的容器(双指针)
        /// </summary>
        /// <param name="height"></param>
        /// <returns></returns>
        public int MaxArea(int[] height)
        {
            int left = 0, right = height.Length - 1;
            int res = 0;
            while (left < right)
            {
                int cur = Math.Min(height[left], height[right]) * (right - left);
                res = Math.Max(res, cur);
                if (height[left] > height[right]) right--;
                else left++;
            }
            return res;
        }

        /// <summary>
        /// leetcode  2864  最大二进制奇数
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public string MaximumOddBinaryNumber(string s)
        {
            char[] nums = s.ToCharArray();
            int left = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] == '1')
                {
                    nums[i] = nums[left];
                    nums[left] = '1';
                    left++;
                }
            }
            nums[left - 1] = nums[nums.Length - 1];
            nums[nums.Length - 1] = '1';

            return string.Join("", nums);
        }

        /// <summary>
        /// leetcode  2575  找出字符串的可整除数组
        /// </summary>
        /// <param name="word"></param>
        /// <param name="m"></param>
        /// <returns></returns>
        public int[] DivisibilityArray(string word, int m)
        {
            int n = word.Length;
            int[] res = new int[n];
            long temp = 0;
            for (int i = 0; i < n; i++)
            {
                int curNum = word[i] - '0';
                temp = (temp * 10 + curNum) % m;
                res[i] = temp == 0 ? 1 : 0;
            }

            return res;
        }

        // leetcode  232  用栈实现队列
        #region 232  用栈实现队列
        public class MyQueue
        {
            Stack<int> stackIn;
            Stack<int> stackOut;
            public MyQueue()
            {
                stackIn = new Stack<int>();
                stackOut = new Stack<int>();
            }

            public void Push(int x)
            {
                stackIn.Push(x);
            }

            public int Pop()
            {
                if (stackOut.Count == 0)
                {
                    while (stackIn.Count > 0)
                    {
                        stackOut.Push(stackIn.Pop());
                    }
                }
                return stackOut.Pop();
            }

            public int Peek()
            {
                if (stackOut.Count == 0)
                {
                    while (stackIn.Count > 0)
                    {
                        stackOut.Push(stackIn.Pop());
                    }
                }
                return stackOut.Peek();
            }

            public bool Empty()
            {
                return stackOut.Count == 0 && stackIn.Count == 0;
            }
        }
        #endregion

        // leetcode  225  用队列实现栈
        #region leetcode  225  用队列实现栈

        public class MyStack
        {
            Queue<int> queue;

            public MyStack()
            {
                queue = new Queue<int>();
            }

            void Push(int x)
            {
                int n = queue.Count;
                queue.Enqueue(x);
                for (int i = 0; i < n; i++)
                {
                    queue.Enqueue(queue.Dequeue());
                }
            }

            int Pop()
            {
                return queue.Dequeue();
            }

            int Top()
            {
                return queue.Peek();
            }

            bool Empty()
            {
                return queue.Count == 0;
            }
        }
        #endregion



        /// <summary>
        /// leetcode  299  猜数字
        /// </summary>
        /// <param name="secret"></param>
        /// <param name="guess"></param>
        /// <returns></returns>
        public string GetHint(string secret, string guess)
        {
            int rightCount = 0, wrongCount = 0;
            int[] secretNum = new int[10];
            int[] guessNum = new int[10];

            for (int i = 0; i < secret.Length; i++)
            {
                if (secret[i] == guess[i])
                    rightCount++;
                else
                {
                    secretNum[secret[i] - '0']++;
                    guessNum[guess[i] - '0']++;
                }
            }

            for (int i = 0; i < 10; i++)
            {
                wrongCount += Math.Min(secretNum[i], guessNum[i]);
            }

            StringBuilder ss = new StringBuilder();
            ss.Append(rightCount);
            ss.Append('A');
            ss.Append(wrongCount);
            ss.Append('B');
            return ss.ToString();
        }

        /// <summary>
        /// leetcode  2129  将标题首字母大写
        /// </summary>
        /// <param name="title"></param>
        /// <returns></returns>
        public string CapitalizeTitle(string title)
        {
            string[] words = title.Split(' ');
            for (int i = 0; i < words.Length; i++)
            {
                if (words[i].Length > 2)
                {
                    char[] chars = words[i].ToCharArray();
                    chars[0] = char.ToUpper(chars[0]);
                    for (int j = 1; j < chars.Length; j++)
                    {
                        chars[j] = char.ToLower(chars[j]);
                    }
                    words[i] = string.Join("", chars);
                }
                else
                {
                    char[] chars = words[i].ToCharArray();
                    for (int j = 0; j < chars.Length; j++)
                    {
                        chars[j] = char.ToLower(chars[j]);
                    }
                    words[i] = string.Join("", chars);
                }
            }

            return string.Join(" ", words);
        }

        /// <summary>
        /// leetcode  54  螺旋矩阵
        /// </summary>
        /// <param name="matrix"></param>
        /// <returns></returns>
        public IList<int> SpiralOrder(int[][] matrix)
        {
            int m = matrix.Length;
            int n = matrix[0].Length;
            int count = m * n;              // 总长度
            int index = 0;                  // 每次填入的下标
            int offset = 1;                 // 空出的长度
            int x = 0, y = 0;               // 初始位置
            int[] res = new int[count];
            while (index < count)
            {
                int i = x, j = y;

                // 上边从左到右
                for (; j < n - offset; j++)
                {
                    res[index++] = matrix[i][j];
                }
                // 右边从上到下
                for (; i < m - offset; i++)
                {
                    res[index++] = matrix[i][j];
                }
                // 下边从右到左
                for (; j > y; j--)
                {
                    res[index++] = matrix[i][j];
                    if (index == count) break;
                }
                // 左边从下到上
                for (; i > x; i--)
                {
                    res[index++] = matrix[i][j];
                    if (index == count) break;
                }

                offset++;
                x++;
                y++;
            }
            if (index == count)
            {
                res[index] = matrix[x][y];
            }

            return res;
        }

        /// <summary>
        /// leetcode  59  螺旋矩阵2
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public int[][] GenerateMatrix(int n)
        {
            int[][] res = new int[n][];
            for (int i = 0; i < n; i++)
            {
                res[i] = new int[n];
            }
            int loop = n / 2;               // 循环次数
            int count = 1;                  // 每次填入的值
            int offset = 1;                 // 空出的长度
            int x = 0, y = 0;               // 初始位置
            while (offset <= loop)
            {
                int i = x, j = y;

                // 上边从左到右
                for (; j < n - offset; j++)
                {
                    res[i][j] = count++;
                }
                // 右边从上到下
                for (; i < n - offset; i++)
                {
                    res[i][j] = count++;
                }
                // 下边从右到左
                for (; j > y; j--)
                {
                    res[i][j] = count++;
                }
                // 左边从下到上
                for (; i > x; i--)
                {
                    res[i][j] = count++;
                }

                offset++;
                x++;
                y++;
            }
            if (n % 2 != 0)
            {
                res[x][y] = count;
            }

            return res;
        }

        /// <summary>
        /// leetcode  209  长度最小的子数组
        /// </summary>
        /// <param name="target"></param>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int MinSubArrayLen(int target, int[] nums)
        {
            int sum = 0;
            int length = nums.Length;
            int res = int.MaxValue;
            for (int i = 0; i < length; i++)
            {
                sum += nums[i];
            }
            if (sum == target)
                return length;
            else if (sum > target)
            {
                int left = 0, right = 0;
                sum = 0;
                while (right < length)
                {
                    sum += nums[right];
                    while (sum >= target)
                    {
                        if (sum == target)
                        {
                            if (right - left + 1 < res) res = right - left + 1;
                        }
                        sum -= nums[left];
                        left++;
                    }
                    right++;
                }
            }
            return res == int.MaxValue ? 0 : res;
        }

        /// <summary>
        /// leetcode  977  有序数组的平方
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int[] SortedSquares(int[] nums)
        {
            int length = nums.Length;
            int[] res = new int[length];
            if (nums.Length != 0)
            {
                if (nums[0] >= 0)
                {
                    for (int i = 0; i < length; i++)
                    {
                        res[i] = nums[i] * nums[i];
                    }
                }
                else if (nums[length - 1] <= 0)
                {
                    for (int i = 0; i < length; i++)
                    {
                        res[length - 1 - i] = nums[i] * nums[i];
                    }
                }
                else
                {
                    length--;
                    for (int left = 0, right = length - 1; left <= right;)
                    {
                        int leftMul = nums[left] * nums[left];
                        int rightMul = nums[right] * nums[right];
                        if (leftMul < rightMul)
                        {
                            res[length] = rightMul;
                            right--;
                        }
                        else
                        {
                            res[length] = leftMul;
                            left++;
                        }
                        length--;
                    }
                }
            }
            return res;
        }

        /// <summary>
        /// leetcode  27  移除元素
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="val"></param>
        /// <returns></returns>
        public int RemoveElement(int[] nums, int val)
        {
            int left = 0;
            int right = nums.Length - 1;
            while (left < right)
            {
                if (nums[left] == val)
                {
                    int temp = nums[left];
                    nums[left] = nums[right];
                    nums[right] = temp;
                    right--;
                }
                else
                {
                    left++;
                }
            }

            return right + 1;
        }

        /// <summary>
        /// leetcode  704  二分查找
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public int Search(int[] nums, int target)
        {
            int left = 0;
            int right = nums.Length - 1;
            while (left <= right)
            {
                int mid = (left + right) / 2;
                int searchNum = nums[mid];
                if (searchNum == target)
                {
                    return mid;
                }
                else if (searchNum > target)
                {
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            return -1;
        }

        /// <summary>
        /// leetcode  187  重复的DNA序列(hash + 滑动窗口)
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public IList<string> FindRepeatedDnaSequences(string s)
        {
            if (s.Length < 10) return new List<string>();
            IList<string> res = new List<string>();
            Dictionary<string, int> dic = new Dictionary<string, int>();
            for (int i = 0; i <= s.Length - 10; i++)
            {
                string temp = s.Substring(i, 10);
                if (dic.ContainsKey(temp))
                    dic[temp]++;
                else
                    dic.Add(temp, 1);
                if (dic[temp] == 2)
                    res.Add(temp);
            }
            return res;
        }

        /// <summary>
        /// leetcode  2103  环和杆
        /// </summary>
        /// <param name="rings"></param>
        /// <returns></returns>
        public int CountPoints(string rings)
        {
            int res = 0;
            int[] rod = new int[10];
            int n = rings.Length / 2;
            for (int i = 0; i < rings.Length; i += 2)
            {
                if (rings[i] == 'R')
                    rod[rings[i + 1] - 48] = 1;
            }
            for (int i = 0; i < rings.Length; i += 2)
            {
                if (rod[rings[i + 1] - 48] == 1 && rings[i] == 'G')
                    rod[rings[i + 1] - 48] = 2;
            }
            for (int i = 0; i < rings.Length; i += 2)
            {
                if (rod[rings[i + 1] - 48] == 2 && rings[i] == 'B')
                    rod[rings[i + 1] - 48] = 3;
            }
            for (int i = 0; i < 10; i++)
            {
                if (rod[i] == 3) res++;
            }
            return res;
        }

        /// <summary>
        /// leetcode  2003  每棵子树内缺失的最小基因值(DFS)
        /// </summary>
        /// <param name="parents"></param>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int[] SmallestMissingValueSubtree(int[] parents, int[] nums)
        {
            int n = parents.Length;
            List<int>[] children = new List<int>[n];
            for (int i = 0; i < n; i++)
            {
                children[i] = new List<int>();
            }
            for (int i = 1; i < n; i++)
            {
                children[parents[i]].Add(i);
            }

            int[] res = new int[n];
            Array.Fill(res, 1);
            bool[] visited = new bool[n];
            ISet<int> set = new HashSet<int>();
            int iNode = 1, node = -1;
            for (int i = 0; i < n; i++)
            {
                if (nums[i] == 1)
                {
                    node = i;
                    break;
                }
            }
            while (node != -1)
            {
                DFSSmallestMissingValueSubtree(nums, children, set, node, visited);
                while (set.Contains(iNode)) iNode++;
                res[node] = iNode;
                node = parents[node];
            }
            return res;
        }

        void DFSSmallestMissingValueSubtree(int[] nums, List<int>[] children, ISet<int> set, int node, bool[] visited)
        {
            if (visited[node]) return;
            visited[node] = true;
            set.Add(nums[node]);
            foreach (var child in children[node])
            {
                DFSSmallestMissingValueSubtree(nums, children, set, child, visited);
            }
        }

        /// <summary>
        /// leetcode  275  H指数2
        /// </summary>
        /// <param name="citations"></param>
        /// <returns></returns>
        public int HIndex2(int[] citations)
        {
            int low = 0, high = citations.Length - 1;
            while (low <= high)
            {
                int index = (low + high) / 2;
                if (citations[index] > citations.Length - index)
                    high = index - 1;
                else if (citations[index] < citations.Length - index)
                    low = index + 1;
                else
                    return citations.Length - index;
            }
            return citations.Length - low;
        }

        /// <summary>
        /// leetcode  274  H指数
        /// </summary>
        /// <param name="citations"></param>
        /// <returns></returns>
        public int HIndex(int[] citations)
        {
            Array.Sort(citations, (a, b) => b - a);
            for (int i = 0; i < citations.Length; i++)
            {
                if (citations[i] < i + 1) return i;
            }
            return citations.Length;
        }

        /// <summary>
        /// leetcode  2558  从数量最多的堆取走礼物(大顶堆)
        /// </summary>
        /// <param name="gifts"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public long PickGifts(int[] gifts, int k)
        {
            PriorityQueue<int, int> queue = new PriorityQueue<int, int>();
            long res = 0;
            foreach (int gift in gifts)
            {
                queue.Enqueue(gift, -gift);
                res += gift;
            }
            for (int i = 0; i < k; i++)
            {
                int gift = queue.Dequeue();
                int next = (int)Math.Sqrt(gift);
                res -= gift - next;
                queue.Enqueue(next, -next);
            }

            return res;
        }

        /// <summary>
        /// leetcode  2520  统计能整除数字的位数
        /// </summary>
        /// <param name="num"></param>
        /// <returns></returns>
        public int CountDigits(int num)
        {
            int copy = num;
            int cur;
            int res = 0;
            while (num > 0)
            {
                cur = num % 10;
                if (copy % cur == 0) res++;
                num /= 10;
            }
            return res;
        }

        /// <summary>
        /// leetcode  1155  掷骰子等于目标和的方法数
        /// </summary>
        /// <param name="n"></param>
        /// <param name="k"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public int NumRollsToTarget(int n, int k, int target)
        {
            if (target < n || target > n * k) return 0;
            int mod = 1000000007;

            int[][] dp = new int[n + 1][];
            for (int i = 0; i <= n; i++)
            {
                dp[i] = new int[target + 1];
            }
            dp[0][0] = 1;
            for (int i = 1; i <= n; i++)
            {
                for (int j = 0; j <= target; j++)
                {
                    for (int x = 1; x <= k; x++)
                    {
                        if (j - x >= 0)
                            dp[i][j] = (dp[i][j] + dp[i - 1][j - x]) % mod;
                    }
                }
            }
            return dp[n][target];
        }

        /// <summary>
        /// leetcode  2678  老人的数目
        /// </summary>
        /// <param name="details"></param>
        /// <returns></returns>
        public int CountSeniors(string[] details)
        {
            int res = 0;
            foreach (string s in details)
            {
                if (int.Parse(s.Substring(11, 2)) > 60) res++;
            }
            return res;
        }

        /// <summary>
        /// leetcode  2525  根据规则将箱子分类
        /// </summary>
        /// <param name="length"></param>
        /// <param name="width"></param>
        /// <param name="height"></param>
        /// <param name="mass"></param>
        /// <returns></returns>
        public string CategorizeBox(int length, int width, int height, int mass)
        {
            bool isBulky = false, isHeavy = false;
            if (length >= 10000 || width >= 10000 || height >= 10000) isBulky = true;
            else if ((long)length * width * height >= 1000000000L) isBulky = true;

            if (mass >= 100) isHeavy = true;

            if (isBulky && isHeavy) return "Both";
            else if (isBulky) return "Bulky";
            else if (isHeavy) return "Heavy";

            return "Neither";
        }

        /// <summary>
        /// leetcode  84  柱状图中最大的矩形(单调栈)
        /// </summary>
        /// <param name="heights"></param>
        /// <returns></returns>
        public int LargestRectangleArea(int[] heights)
        {
            int n = heights.Length;
            Stack<int> stack = new Stack<int>();
            int[] newHeights = new int[n + 2];
            for (int i = 0; i < n; i++)
            {
                newHeights[i + 1] = heights[i];
            }
            stack.Push(0);
            int res = 0;
            for (int i = 1; i < n; i++)
            {
                while (stack.Count > 0 && newHeights[i] < newHeights[stack.Peek()])
                {
                    int mid = stack.Pop();
                    if (stack.Count > 0)
                    {
                        int h = newHeights[mid];
                        int w = i - stack.Peek() - 1;
                        res = Math.Max(res, w * h);
                    }
                }
                stack.Push(i);
            }
            return res;
        }

        /// <summary>
        /// leetcode  42  接雨水(双指针 / 单调栈)
        /// </summary>
        /// <param name="height"></param>
        /// <returns></returns>
        public int Trap(int[] height)
        {
            #region 双指针
            //int n = height.Length;
            //if (n <= 2) return 0;
            //int[] left = new int[n], right = new int[n];
            //left[0] = height[0];
            //right[n - 1] = height[n - 1];
            //for (int i = 1; i < n; i++)
            //    left[i] = Math.Max(left[i - 1], height[i]);

            //for (int i = n - 2; i >= 0; i--)
            //    right[i] = Math.Max(height[i], right[i + 1]);

            //int res = 0;
            //for (int i = 1; i < n; i++)
            //    res += Math.Min(left[i], right[i]) - height[i];

            //return res; 
            #endregion

            int n = height.Length;
            if (n <= 2) return 0;
            Stack<int> stack = new Stack<int>();
            stack.Push(0);
            int res = 0;
            for (int i = 1; i < n; i++)
            {
                while (stack.Count > 0 && height[i] > height[stack.Peek()])
                {
                    int mid = stack.Pop();
                    if (stack.Count > 0)
                    {
                        int h = Math.Min(height[stack.Peek()], height[i]) - height[mid];
                        int w = i - stack.Peek() - 1;
                        res += h * w;
                    }
                }
                stack.Push(i);
            }
            return res;
        }

        /// <summary>
        /// leetcode  503  下一个更大元素2(单调栈)
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int[] NextGreaterElements2(int[] nums)
        {
            int n = nums.Length;
            int[] ans = new int[n];
            Stack<int> stack = new Stack<int>();
            Array.Fill(ans, -1);
            for (int i = 0; i < n * 2; i++)
            {
                int index = i % n;
                while (stack.Count > 0 && nums[index] > nums[stack.Peek()])
                {
                    ans[stack.Peek()] = nums[index];
                    stack.Pop();
                }
                stack.Push(index);
            }
            return ans;
        }

        /// <summary>
        /// leetcode  1726  同积元组
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int TupleSameProduct(int[] nums)
        {
            int res = 0;
            Dictionary<int, int> productCount = new Dictionary<int, int>();
            int n = nums.Length;
            for (int i = 0; i < n; i++)
            {
                for (int j = i + 1; j < n; j++)
                {
                    int product = nums[i] * nums[j];
                    if (productCount.ContainsKey(product))
                        productCount[product]++;
                    else
                        productCount.Add(product, 1);
                }
            }
            foreach (var item in productCount)
            {
                int value = item.Value;
                if (value > 1)
                {
                    res += value * (value - 1) * 4;
                }
            }
            return res;
        }

        /// <summary>
        /// leetcode  496  下一个更大元素1(单调栈)
        /// </summary>
        /// <param name="nums1"></param>
        /// <param name="nums2"></param>
        /// <returns></returns>
        public int[] NextGreaterElement(int[] nums1, int[] nums2)
        {
            int n = nums1.Length;
            int[] ans = new int[n];
            Dictionary<int, int> map = new Dictionary<int, int>();
            Stack<int> stack = new Stack<int>();
            for (int i = 0; i < n; i++)
            {
                ans[i] = -1;
                map.Add(nums1[i], i);
            }
            for (int i = 0; i < nums2.Length; i++)
            {
                if (stack.Count > 0 && nums2[i] > nums2[stack.Peek()])
                {
                    if (map.ContainsKey(nums2[stack.Peek()]))
                    {
                        ans[map[nums2[stack.Peek()]]] = nums2[i];
                    }
                    stack.Pop();
                }
                stack.Push(i);
            }
            return ans;
        }

        /// <summary>
        /// leetcode  2530  执行K次操作后的最大分数(优先队列)
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public long MaxKelements(int[] nums, int k)
        {
            long res = 0;
            PriorityQueue<int, int> queue = new PriorityQueue<int, int>();
            foreach (int num in nums)
                queue.Enqueue(num, -num);

            for (int i = 0; i < k; i++)
            {
                int cur = queue.Dequeue();
                res += cur;
                queue.Enqueue((cur + 2) / 3, -(cur + 2) / 3);
            }
            return res;
        }

        /// <summary>
        /// leetcode  739  每日温度(单调栈)
        /// </summary>
        /// <param name="temperatures"></param>
        /// <returns></returns>
        public int[] DailyTemperatures(int[] temperatures)
        {
            int n = temperatures.Length;
            int[] res = new int[n];
            Stack<int> stack = new Stack<int>();
            for (int i = 0; i < n; i++)
            {
                while (stack.Count > 0 && temperatures[stack.Peek()] < temperatures[i])
                {
                    res[stack.Peek()] = i - stack.Peek();
                    stack.Pop();
                }
                stack.Push(i);
            }
            return res;
        }

        /// <summary>
        /// leetcode  136  只出现一次的数字(异或)
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int SingleNumber(int[] nums)
        {
            int res = 0;
            foreach (int x in nums) res ^= x;
            return res;
        }

        /// <summary>
        /// leetcode  13  罗马数字转整数
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public int RomanToInt(string s)
        {
            Dictionary<char, int> dict = new Dictionary<char, int>();
            dict.Add('M', 1000);
            dict.Add('D', 500);
            dict.Add('C', 100);
            dict.Add('L', 50);
            dict.Add('X', 10);
            dict.Add('V', 5);
            dict.Add('I', 1);

            int res = 0;
            int n = s.Length;
            for (int i = 0; i < n; i++)
            {
                int value = dict[s[i]];
                if (i < n - 1 && value < dict[s[i + 1]])
                {
                    res -= value;
                }
                else
                    res += value;
            }

            return res;
        }

        /// <summary>
        /// leetcode  1488  避免洪水泛滥(未完成)
        /// </summary>
        /// <param name="rains"></param>
        /// <returns></returns>
        public int[] AvoidFlood(int[] rains)
        {
            int n = rains.Length;
            int[] ans = new int[n];
            Array.Fill(ans, 1);

            Dictionary<int, int> fullWeak = new Dictionary<int, int>();
            SortedSet<int> sunny = new SortedSet<int>();

            for (int i = 0; i < n; i++)
            {
                if (rains[i] == 0)
                {
                    if (fullWeak.Count > 0)
                        sunny.Add(i);
                }
                else
                {
                    ans[i] = -1;
                    if (fullWeak.ContainsKey(rains[i]))
                    {
                        if (sunny.Count > 0)
                        {
                        }
                        else
                            return new int[] { };
                    }
                    else
                    {
                        fullWeak.Add(rains[i], i);
                    }

                }
            }

            return ans;
        }

        /// <summary>
        /// leetcode  12  整数转罗马数字
        /// </summary>
        /// <param name="num"></param>
        /// <returns></returns>
        public string IntToRoman(int num)
        {
            Dictionary<int, string> dict = new Dictionary<int, string>();
            dict.Add(1000, "M");
            dict.Add(900, "CM");
            dict.Add(500, "D");
            dict.Add(400, "CD");
            dict.Add(100, "C");
            dict.Add(90, "XC");
            dict.Add(50, "L");
            dict.Add(40, "XL");
            dict.Add(10, "X");
            dict.Add(9, "IX");
            dict.Add(5, "V");
            dict.Add(4, "IV");
            dict.Add(1, "I");

            StringBuilder sb = new StringBuilder();

            foreach (var item in dict)
            {
                int key = item.Key;
                while (num >= key)
                {
                    sb.Append(item.Value);
                    num -= key;
                }
                if (num == 0) break;
            }

            return sb.ToString();
        }

        /// <summary>
        /// leetcode  2562  找出数组的串联值
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public long FindTheArrayConcVal(int[] nums)
        {
            long res = 0;
            int left = 0;
            int right = nums.Length - 1;
            while (left < right)
            {
                string temp = "" + nums[left] + nums[right];
                res += long.Parse(temp);
                left++;
                right--;
            }
            if (left == right)
                res += nums[left];

            return res;
        }

        /// <summary>
        /// leetcode  2512  奖励最顶尖的 K 名学生
        /// </summary>
        /// <param name="positive_feedback"></param>
        /// <param name="negative_feedback"></param>
        /// <param name="report"></param>
        /// <param name="student_id"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public IList<int> TopStudents(string[] positive_feedback, string[] negative_feedback, string[] report, int[] student_id, int k)
        {
            Dictionary<string, int> feedback = new Dictionary<string, int>();

            foreach (var item in positive_feedback)
            {
                feedback.TryAdd(item, 3);
            }

            foreach (var item in negative_feedback)
            {
                feedback.TryAdd(item, -1);
            }

            int n = report.Length;
            int[][] scores = new int[n][];

            for (int i = 0; i < student_id.Length; i++)
            {
                int tempScore = 0;
                string[] words = report[i].Split(' ');
                foreach (var word in words)
                {
                    tempScore += feedback.ContainsKey(word) ? feedback[word] : 0;
                }
                scores[i] = new int[] { student_id[i], tempScore };
            }
            Array.Sort(scores, (a, b) =>
            {
                if (a[1] == b[1]) return a[0] - b[0];
                return b[1] - a[1];
            });

            IList<int> res = new List<int>();
            for (int i = 0; i < k; i++)
            {
                res.Add(scores[i][0]);
            }
            return res;
        }

        /// <summary>
        /// leetcode  2731  移动机器人
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="s"></param>
        /// <param name="d"></param>
        /// <returns></returns>
        public int SumDistance(int[] nums, string s, int d)
        {
            int mod = 1000000007;
            int n = nums.Length;
            long[] pos = new long[n];
            for (int i = 0; i < n; i++)
            {
                if (s[i] == 'L')
                    pos[i] = nums[i] - d;
                else
                    pos[i] = nums[i] + d;
            }
            Array.Sort(pos);
            long res = 0;
            for (int i = 1; i < n; i++)
            {
                res += (pos[i] - pos[i - 1]) * i % mod * (n - i) % mod;
                res %= mod;
            }

            return (int)res;
        }

        /// <summary>
        /// leetcode  2578  最小和切割(贪心)
        /// </summary>
        /// <param name="num"></param>
        /// <returns></returns>
        public int SplitNum(int num)
        {
            char[] strNums = num.ToString().ToCharArray();
            Array.Sort(strNums);
            int num1 = 0, num2 = 0;

            for (int i = 0; i < strNums.Length; i++)
            {
                if (i % 2 == 0)
                    num1 = num1 * 10 + (strNums[i] - '0');
                else
                    num2 = num2 * 10 + (strNums[i] - '0');
            }
            return num1 + num2;
        }

        /// <summary>
        /// leetcode  901  股票价格跨度
        /// </summary>
        public class StockSpanner
        {
            Stack<Tuple<int, int>> stack;
            int index;

            public StockSpanner()
            {
                stack = new Stack<Tuple<int, int>>();
                stack.Push(new Tuple<int, int>(0, int.MaxValue));
                index = 0;
            }

            public int Next(int price)
            {
                index++;
                while (price >= stack.Peek().Item2)
                {
                    stack.Pop();
                }
                int ret = index - stack.Peek().Item1;
                stack.Push(new Tuple<int, int>(index, price));
                return ret;
            }
        }

        /// <summary>
        /// leetcode  2251  花期内花的数目
        /// </summary>
        /// <param name="flowers"></param>
        /// <param name="people"></param>
        /// <returns></returns>
        public int[] FullBloomFlowers(int[][] flowers, int[] people)
        {
            int n = flowers.Length;
            int[] start = new int[n];
            int[] end = new int[n];
            for (int i = 0; i < n; i++)
            {
                start[i] = flowers[i][0];
                end[i] = flowers[i][1];
            }
            Array.Sort(start);
            Array.Sort(end);
            int m = people.Length;
            int[] answer = new int[m];
            for (int i = 0; i < m; i++)
            {
                int next = BinarySearchFlower(start, people[i] + 1);
                int pre = BinarySearchFlower(end, people[i]);
                answer[i] = next - pre;
            }
            return answer;
        }

        int BinarySearchFlower(int[] nums, int target)
        {
            int res = nums.Length;
            int left = 0;
            int right = nums.Length - 1;
            while (left <= right)
            {
                int mid = (left + right) / 2;
                if (nums[mid] >= target)
                {
                    res = mid;
                    right = mid - 1;
                }
                left = mid + 1;
            }
            return res;
        }

        /// <summary>
        /// leetcode  1333  餐厅过滤器
        /// </summary>
        /// <param name="restaurants"></param>
        /// <param name="veganFriendly"></param>
        /// <param name="maxPrice"></param>
        /// <param name="maxDistance"></param>
        /// <returns></returns>
        public IList<int> FilterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance)
        {
            IList<int[]> filter = new List<int[]>();
            int n = restaurants.Length;
            bool veganFilter = veganFriendly == 1;
            foreach (int[] item in restaurants)
            {
                if (!(veganFilter && item[2] == 0) && item[3] <= maxPrice && item[4] <= maxDistance)
                    filter.Add(item);
            }

            int[][] filterArr = filter.ToArray();
            Array.Sort(filterArr, (a, b) =>
            {
                if (a[1] == b[1]) return b[0] - a[0];
                return b[1] - a[1];
            });
            IList<int> res = new List<int>();
            foreach (int[] item in filterArr)
            {
                res.Add(item[0]);
            }
            return res;
        }

        /// <summary>
        /// leetcode  2582  递枕头
        /// </summary>
        /// <param name="n"></param>
        /// <param name="time"></param>
        /// <returns></returns>
        public int PassThePillow(int n, int time)
        {
            if (n == 1)
                return n;
            int res = 1;
            int dir = 1;
            while (time > 0)
            {
                res += dir;
                time--;
                if (res == 1 || res == n)
                    dir *= -1;
            }
            return res;
        }

        /// <summary>
        /// leetcode  LCP 50  宝石补给
        /// </summary>
        /// <param name="gem"></param>
        /// <param name="operations"></param>
        /// <returns></returns>
        public int GiveGem(int[] gem, int[][] operations)
        {
            int max = -1;
            int min = int.MaxValue;
            foreach (var swap in operations)
            {
                int temp = gem[swap[0]] / 2;
                gem[swap[0]] -= temp;
                gem[swap[1]] += temp;
            }
            for (int i = 0; i < gem.Length; i++)
            {
                if (gem[i] < min)
                    min = gem[i];
                else if (gem[i] > max)
                    max = gem[i];
            }

            return max - min;
        }

        /// <summary>
        /// leetcode  1222  可以攻击国王的皇后
        /// </summary>
        /// <param name="queens"></param>
        /// <param name="king"></param>
        /// <returns></returns>
        public IList<IList<int>> QueensAttacktheKing(int[][] queens, int[] king)
        {
            IList<IList<int>> res = new List<IList<int>>();
            if (queens.Length == 0)
            {
                return res;
            }
            int[][] grid = new int[8][];
            for (int i = 0; i < 8; i++)
            {
                grid[i] = new int[8];
            }
            foreach (int[] q in queens)
            {
                grid[q[0]][q[1]] = 1;
            }

            int row = king[0];
            int col = king[1];
            SearchQueens(res, grid, row - 1, col, 1);
            SearchQueens(res, grid, row + 1, col, 2);
            SearchQueens(res, grid, row, col - 1, 3);
            SearchQueens(res, grid, row, col + 1, 4);
            SearchQueens(res, grid, row - 1, col - 1, 5);
            SearchQueens(res, grid, row - 1, col + 1, 6);
            SearchQueens(res, grid, row + 1, col - 1, 7);
            SearchQueens(res, grid, row + 1, col + 1, 8);

            return res;
        }
        static void SearchQueens(IList<IList<int>> res, int[][] grid, int row, int col, int dir)
        {
            if (row < 0 || row >= 8 || col < 0 || col >= 8)
                return;
            if (grid[row][col] == 1)
            {
                res.Add(new List<int> { row, col });
                return;
            }
            else
            {
                switch (dir)
                {
                    case 1:
                        SearchQueens(res, grid, row - 1, col, 1);
                        break;
                    case 2:
                        SearchQueens(res, grid, row + 1, col, 2);
                        break;
                    case 3:
                        SearchQueens(res, grid, row, col - 1, 3);
                        break;
                    case 4:
                        SearchQueens(res, grid, row, col + 1, 4);
                        break;
                    case 5:
                        SearchQueens(res, grid, row - 1, col - 1, 5);
                        break;
                    case 6:
                        SearchQueens(res, grid, row - 1, col + 1, 6);
                        break;
                    case 7:
                        SearchQueens(res, grid, row + 1, col - 1, 7);
                        break;
                    case 8:
                        SearchQueens(res, grid, row + 1, col + 1, 8);
                        break;
                    default: break;
                }
            }
        }

    }

    public class LockingTree
    {
        public int nearParent;
        int[] parent;
        int[] lockUser;
        Dictionary<int, HashSet<int>> children;



        public LockingTree(int[] parent)
        {
            int n = parent.Length;
            this.parent = parent;
            lockUser = new int[n];
            children = new Dictionary<int, HashSet<int>>();
            for (int i = -1; i < n; i++)
            {
                children.Add(i, new HashSet<int>());
            }
            for (int i = 0; i < n; i++)
            {
                children[parent[i]].Add(i);
            }
        }

        public bool Lock(int num, int user)
        {
            if (lockUser[num] == 0)
            {
                lockUser[num] = user;
                return true;
            }
            return false;
        }

        public bool Unlock(int num, int user)
        {
            if (lockUser[num] == user)
            {
                lockUser[num] = 0;
                return true;
            }
            return false;
        }

        public bool Upgrade(int num, int user)
        {
            int find = num;
            while (find != -1)
            {
                if (lockUser[find] != 0)
                    return false;
                find = parent[find];
            }


            int lockChildren = 0;
            Queue<int> queue = new Queue<int>();
            queue.Enqueue(num);
            while (queue.Count > 0)
            {
                foreach (var item in children[queue.Dequeue()])
                {
                    if (lockUser[item] != 0)
                    {
                        lockChildren++;
                        lockUser[item] = 0;
                    }
                    queue.Enqueue(item);
                }
            }
            if (lockChildren > 0)
            {
                lockUser[num] = user;
                return true;
            }
            return false;
        }
    }
}
